   IOI. 2 (Joc patratic). Se da o matrice 4x4 ale carei celule contin (n mod 
normal) numerele de la 1 la 14, cu exceptia a doua dintre ele care contin 0 
(sunt libere).
Exemplu:
              Matricea A                                         Matricea B

                7  3  5 14                                        1  2  3  4
                0  4  9 13                                        5  6  7  8
                1  0  2 10                                        9 10 11 12
               11  8 12  6                                       13 14  0  0

  Pentru trecerea de la matricea A, citita de la intrare, la matricea finala B 
se foloseste urmatoarea regula de transformare: orice numar pozitiv poate fi 
deplasat orizontal sau vertical (dar nu pe diagonala) ntr-o celula libera 
alaturata, celula care a continut acest numar devenind libera.
Se cer:
  1. Introducerea si validarea datelor de intrare;
  2. Vizualizarea unui sir de transformari care realizeaza trecerea de la o 
matrice A citita la intrare la matricea finala B, pentru fiecare transformare 
trebuind sa apara numarul ei de ordine, matricea de la care s-a plecat si 
matricea la care s-a ajuns;
  3. Sa se minimizeze numarul de transformari.
================================================
Algoritm:
S[ definim nti doi subalgoritmi. Primul, numit schimb, ntr-o grupare de patru celule, le
interschimb[ pe cele de pe diagonal[. La intrare sunt 4 celule aezate
                                                           A      B
                                                            C      D
unde, sau (i) (A)=(C)=0, sau (ii) (B)=(D)=0 (am notat cu (X) coninutul celulei (X)).
Algoritmul schimb(A,B,C,D) este:
1. Dac[ (B)=0 atunci salt la 3;
2. (D)C;(B)A;(C)B;(A)D;0A;0C;Revenire;
3. (A)D;(C)B;(D)C;(B)A;0B;0D;Revenire;
Al doilea sublagoritm, mutare, va permuta elementele dintr-o grupare de dou[ celule al[turate, din
care una conine 0;
mutare(A,B):
1. Dac[ (B)=0 atunci salt la 3:
2. (B)A;0B; Revenire;
3. (A)B;0A; Revenire;
Acum putem da un algoritm de rezolvare al problemei ioi.2.:
              Algoritm Joc_patratic:
Pas 1: Citete matricea A; 
Pas 2: Pentru fiecare k=1,14:
               2.1: Se determin[ poziia (i0,j0) unde trebuie s[ ajung[ k:
                k div 4  dac[ (k mod 4)c0
  i0= 
               (k div 4)+1   dac[ (k mod 4)=0
                                       k mod 4 dac[ (k mod 4)c0
                 j0
                                       4 dac[ (k mod 4)=0
              2.2: Se determin[ poziia (i,j) pe care se afl[ k n matricea A.
              2.3. In funcie de situaiile care apar, se trateaz[ unul din urm[toarele 9 subcazuri:
2.3.1. i<i0, j<j0;                      2.3.2. i<i0,j=j0;
2.3.3. i<i0,j>j0;                        2.3.4. i=i0,j<j0; 
2.3.5. i=i0,j=j0;                        2.3.6. i=i0,j>j0;
2.3.7. i>i0,j<j0;                        2.3.8. i>i0,j=j0;
2.3.9. i>i0,j>j0;
              Cazul de acceptare este 2.3.5, cnd se reia ciclul pasului 2. In celelalte situaii se caut[ ca
prin folosirea subalgoritmilor schimb i mutare, s[ se aduc[ matricea A la situaia 2.3.5. Vom
detalia algoritmul doar pentru primele trei cazuri, celelalte situaii fiind analoge.
2.3.1. Se aplic[ paii (a),(b),(c) ct timp i<i0,j<j0:
              a) Folosind sublagoritmul mutare se aduc cele dou[ zerouri pe poziiile (i+1,j) respectiv
(i,j+1);
              b) Se aplic[ subalgoritmul schimb pentru celulele:
                                            (i,j),(i,j+1),(i+1,j),(i+1,j+1).
              c) i+1i, j+1j.
In final se ajunge la unul din cazurile:2.3.2, 2.3.4, 2.3.5.
2.3.2. Se aplic[ paii (a),(b),(c) ct timp i<i0:
              a) Folosind sublagoritmul mutare se aduce unul din cele dou[ zerouri pe poziia (i+1,j0);
              b) Se aplic[ subalgoritmul mutare pentru celulele:(i,j0),(i+1,j0).
              c) i+1i.
In final se ajunge la cazul 2.3.5.
2.3.3. Se aplic[ paii (a),(b),(c) ct timp i<i0,j>j0:
              a) Folosind sublagoritmul mutare se aduc cele dou[ zerouri pe poziiile (i+1,j) respectiv
(i,j-1);
              b) Se aplic[ subalgoritmul schimb pentru celulele:
                                            (i,j),(i,j-1),(i+1,j),(i+1,j-1).
              c) i+1i, j-1j.
In final se ajunge la unul din cazurile: 2.3.2, 2.3.5, 2.3.6.

              Pentru minimizarea num[rului de aplic[ri ale subalgorimului mutare (care va conduce la
rezolvarea punctului 3 al problemei), se caut[ s[ se aduc[ pe poziia (i,j) acel 0 aflat pe poziia
(i',j') pentru care |i'-i|+|j'-j| este minim. 
----------------------------------------------
Program:
????????????????????????
